﻿#include <iostream>
#include <vector>
using namespace std;


// 数组中的逆序对
class Solution
{
	int tmp[50020];
public:
	int reversePairs(vector<int>& nums)
	{
		return mergeSort(nums, 0, nums.size() - 1);
	}

	int mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right)
			return 0;

		int ret = 0;
		// 1、找出中间点，将数组划分为两部分
		int mid = (right - left) / 2 + left;
		// 2、左边个数 + 排序 + 右边个数 + 排序
		ret += mergeSort(nums, left, mid);
		ret += mergeSort(nums, mid + 1, right);

		// 3、一左一右个数
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right)
		{
			if(nums[cur1] <= nums[cur2])
			{
				tmp[i++] = nums[cur1++];
			}
			else
			{
				ret += mid - cur1 + 1;
				tmp[i++] = nums[cur2++];
			}
		}

		// 4、处理排序
		while (cur1 <= mid)
			tmp[i++] = nums[cur1++];
		while (cur2 <= right)
			tmp[i++] = nums[cur2++];

		for (int i = left; i <= right; i++)
			nums[i] = tmp[i - left];
		
		return ret;
	}
};

int main()
{
	vector<int> v{ 8,7,5,6,4 };
	cout << Solution().reversePairs(v) << endl;

	return 0;
}